package com.yeung.swordoffer;

import java.util.ArrayList;

/**
 * 题目描述
 * 给定一棵二叉搜索树，请找出其中的第k小的结点。
 * 例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。
 */
public class 二叉搜索树的第k个结点 {
    TreeNode KthNode(TreeNode pRoot, int k) {
        if (k == 0) return null;
        ArrayList<TreeNode> list = new ArrayList<>();
        kthTimes(pRoot, list);
        if (k > list.size()) return null;
        return list.get(k-1);
    }

    void kthTimes(TreeNode pRoot, ArrayList<TreeNode> result) {
        if (pRoot == null) return;
        kthTimes(pRoot.left, result);
        result.add(pRoot);
        kthTimes(pRoot.right, result);
    }
}
